1. Field of the Invention
This invention relates to textual image processing applications, for example document analysis and image understanding systems. More particularly this invention relates to a method of skew detection of textual information which is embedded in noisy digitized gray scale images which also contain non-textual information.
2. Description of the Related Art
De-skewing text in digitized images is a critical preprocessing step in document analysis systems and in image understanding systems. Image acquisition devices such as scanners can convert paper documents into image formats suitable for computers. The transformation of images to text is typically accomplished by text processing units which perform operations of binarization, de-skew, layout analysis, and optical character recognition (xe2x80x9cOCRxe2x80x9d). For optimal performance the input image should be free of skew distortion. Unfortunately, documents are skewed during the scanning process.
In automatic parcel sorting systems, the address is read and decoded while it travels on a conveyor. The addresses on the parcels are located at different locations and positions. In contrast to documents, which often are predominantly textual, and may have redundant data, addresses on parcels contain relatively few characters and few lines. Moreover, addresses are often located in the vicinity of graphics, binding tape, reflecting plastic and other noisy items. Thus, the skew angle detection in the address text becomes very complicated.
It is proposed in the document Automatic Identification and Skew Estimation of Text Lines in Real Scene Images, Messelodi, S. and Modena, C. M., Pattern Recognition 32, pp 791-810 (1999), to automatically localize text embedded in complex images. Following preprocessing, various heuristics are employed to characterize text objects which depend on the geometrical and spatial relations among more elementary components. Text line detection is accomplished by recursive nodal expansion of geometrically related components in the image to develop a tree structure.
Another approach to skew detection is disclosed in the document Skew Detection and Text Line Position Determination in Digitized Documents, Gatos B. et al., Pattern Recognition 30, No. 9, pp 1505-1519 (1997), which attempts to exploit cross correlation between the pixels of vertical lines in a digitized document. A composite correlation matrix is developed for one or more vertical lines, and the skew angle of the document is evaluated from the global maximum of a projection derived from the matrix.
There are disadvantages to the known techniques, particularly when applied to applications where there is limited a priori knowledge of the textual material being captured or evaluated, and where the evaluation is complicated by noise and various non-textual elements.
It is therefore a primary object of the present invention to provide an improved method of deskewing text in composite digitized gray scale images.
It is another object of some aspects of the invention to provide a technique for skew detection to improve the accuracy and efficiency of applications where the skew angle is unconstrained, such as automatic parcel and mail sorting.
These and other objects of the present invention are attained by a method for text skew detection operative in gray scale images, including noisy gray scale images, and at any skew angle, which is performed by smearing a binary digitized image in at least one direction, and determining a skew angle of a dominant text line in the smeared digitized image. Optionally the digitized image is preprocessed by binarization, and by the removal of nontextual components
According to one aspect of the invention selection of a dominant text line is performed by the Hough method, preferably conducted at first and second angular resolutions.
According to another aspect of the invention the image is sampled by selecting start points and end points of runs therein, and the dominant text line is selected from the sampled image.
According to yet another aspect of the invention smearing of the digitized image is performed by smearing the binary digitized image in one of a horizontal direction and a vertical direction to yield a first smeared image, smearing the digitized image in the other of the horizontal direction and the vertical direction to yield a second smeared image, and smearing the digitized image in both the horizontal direction and the vertical direction to yield a third smeared image. One of the first, second and third smeared images is selected according to a minimum number of runs therein. Preferably the selection of the dominant text line is performed on a sampled image, wherein start points and end points of runs in the selected smeared image are sampled.
The invention provides a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to accept as input a digitized image having textual material embedded therein, and to determine at least one skew angle of the textual material by executing a process of binarization, and smearing the binary digitized image in at least one direction, selecting a dominant text line from the smeared image, and determining the skew angle of the dominant text line.
In one aspect of the invention the computer program instructions further cause the computer to binarize the digitized image prior to executing the process of smearing.
In another aspect of the invention the computer program instructions cause the computer to remove nontextual components from the digitized image prior to executing the process of smearing.
In yet another aspect of the invention the computer program instructions cause the computer to select a dominant text line by executing an algorithm according to the Hough method. Preferably the Hough method is executed at first and second angular resolutions
According to still another aspect of the invention the computer program instructions cause the computer to sample start points and end points of runs in the smeared image to yield a sampled image, and to select the dominant text line from the sampling.
Most preferably the computer program instructions further cause the computer to execute the step of smearing by smearing the binary digitized image in one of a horizontal direction and a vertical direction to yield a first smeared image, smearing the binary digitized image in another of the horizontal direction and the vertical direction to yield a second smeared image, and smearing the binary digitized image in both of the horizontal direction and the vertical direction to yield a third smeared image. The computer is caused to select one of the first, second and third smeared images according to a minimum number of runs therein.
The invention provides an automated classification system, which has a conveyance for transporting items to be classified, wherein the items have classification information written thereon. An acquisition device has a field of view directed toward the conveyance for acquiring an image of the classification information. A digitizing unit converts the acquired image to a digitized image. A computer is provided with a program of instructions which causes the computer to accept as input the digitized image, and to determine at least one skew angle of the classification information by the steps of binarization of the image, smearing the binary digitized image in at least one direction, selecting a dominant text line from the smeared digitized image, and determining a skew angle of the dominant text line. An analysis program of the computer accepts the digitized image and the skew angle and evaluates the classification information based on the deskewed image. Control signals are then output from the computer responsive to the analysis program, to control a classifier for classifying the transported items.
According to another aspect of the invention the instructions further cause the computer to select the dominant text line by the Hough method. This is preferably accomplished using a first, coarse angular resolution and then a second, fine angular resolution.
In a further aspect of the invention the instructions further cause the computer to sample start points and end points of runs in the smeared image to yield a sampled image, and selection of a dominant text line is performed on the sampled image. Preferably the digitized image is smeared in one of a horizontal direction and a vertical direction to yield a first smeared image, then smeared in the other of the horizontal direction and the vertical direction to yield a second smeared image, and finally smeared in both the horizontal direction and the vertical direction to yield a third smeared image. One of the first, second and third smeared images is selected according to a minimum number of runs therein.